package cn.orange.ch07_binarytree;

import cn.orange.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * LC501.二叉搜索树中的众数
 */
public class LC501 {
    private TreeNode prev = null;
    private int maxCount = 0;
    private int count = 0;
    private List<Integer> ans = new ArrayList<>();
    public int[] findMode(TreeNode root) {
        traverseTree(root);
        int[] result = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            result[i] = ans.get(i);
        }
        return result;
    }

    private void traverseTree(TreeNode root) {
        if (root == null) return;
        traverseTree(root.left);
        if (prev == null || prev.val != root.val) {
            count = 1;
        } else {
            count++;
        }
        prev = root;
        if (count > maxCount) {
            ans.clear();
            maxCount = count;
        }
        if (count == maxCount) {
            ans.add(root.val);
        }
        traverseTree(root.right);
    }

    public static void main(String[] args) {
        LC501 alg = new LC501();
        TreeNode root1 = new TreeNode(1, null, new TreeNode(2));
        root1.right.left = new TreeNode(2);
        System.out.println(Arrays.toString(alg.findMode(root1)));
    }
}
